This invention relates to a cryptographic verification system in which a transcript of the verification process provides valid evidence that verification actually took place.
Systems based on secret information are widely used to verify the identity of persons using automatic teller machines, computers, and other facilities. In one well-known system a user (referred to as the prover) presents public information such as a name or account number and secret information such as a password to another party (referred to as the verifier). The verifier checks that the public and secret information match on a list, or transmits the public and secret information to a central authority for checking.
A problem in this simple system is that since the verifier learns the prover's secret information, the verifier can later impersonate the prover. Recently a number of zero-knowledge protocols have been proposed that overcome this problem by enabling the prover to demonstrate that he possesses secret information without actually revealing the secret information. These protocols depend on the intractability of certain calculations, such as extracting square roots modulo a large composite number with unknown prime factors.
Although these zero-knowledge protocols prevent the verifier from impersonating the prover, many of them still suffer from the defect that, even without knowing the prover's secret information, the verifier can forge a credible transcript of a verification process. This has two undesirable consequences: one is that the verifier can defraud the prover; another is that the prover can obtain services from the verifier, then deny that these services were received and claim that the verifier's records of the verification process are forgeries.
A further problem of many zero-knowledge protocols is that the prover can forge a plausible transcript of the verification process. This may also have undesirable consequences, e.g. the prover can defraud the verifier, or the verifier can claim that the prover's records are forgeries and the prover cannot disprove this claim.